import java.util.HashSet;

public class MyMap {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    //二叉搜索树：root的左子树比它小，右子树比它大
    public boolean search(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == val) {
                return true;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return false;
    }

    public boolean insert(int val) {
        if(root == null) {
            root = new TreeNode(val);
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            parent = cur;
            if(cur.val == val) {
                return false;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        TreeNode node = new TreeNode(val);
        if(parent.val > val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;

    }

    public boolean remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            parent = cur;
            if(cur.val == val) {
                break;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        if(cur == null) {
            return false;
        }else {
            //删除节点
            removeNode(parent, cur);
            return true;
        }
    }

    //cur是要删除的节点，parent是要删除的节点的父亲节点
    private void removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                cur = cur.right;
            }else if(parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }

        }else if(cur.right == null) {
            if(cur == root) {
                cur = cur.left;
            }else if(parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //两边都不为空
            //所以要么在cur的左树中找一个最大的数据来代替cur/在cur的右树中找一个最小的数据来代替cur
            TreeNode parentTarget = cur;
            TreeNode target = cur.left;
            while(target.right != null) {
                parentTarget = target;
                target = target.right;
            }
            //直接赋值
            cur.val = target.val;

            //删除target节点
            if(parentTarget.left == target) {
                parentTarget.left = target.left;
            }else {
                parentTarget.right = target.left;
            }

        }
    }




}

class HashBucket {

    static class Node {
        private int val;
        private int key;
        private Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node[] arr;
    private int usedSize;
    public HashBucket() {
        arr = new Node[10];
    }

    //负载因子
    private float DEFAULT_FACTOR = 0.75f;

    private float factor() {
        return usedSize * 1.0f / arr.length;
    }
    public void put(int key, int val) {
        int index = key % arr.length;
        Node cur = arr[index];
        while(cur != null) {
            if(cur.key == key) {
                //更新value
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        //遍历完index下标的链表发现没有key，则在index位置的链表进行头插法
        Node node = new Node(key, val);
        node.next = arr[index];
        arr[index] = node;
        usedSize++;

        if(factor() > DEFAULT_FACTOR) {
            //扩容
            reSize();
        }
    }

    private void reSize() {
        Node[] newArray = new Node[2 * arr.length];
        for(int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while(cur != null) {
                Node tmp = cur.next;
                int index = cur.key % newArray.length;
                cur.next = arr[index];
                arr[index] = cur;
                cur = tmp;
            }
        }
        arr = newArray;
    }

    //找元素
    public int get(int key) {
        int index = key % arr.length;
        Node cur = arr[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        //表示没有找到
        return -1;
    }

    public static void main(String[] args) {
        HashSet<Character> set = new HashSet<>();
    }

}
